
#include <iostream>
#include <sstream>
#include <fstream>
#include "stdafx.h"
#include "Solver.h"
#include "Settings.h"
#include <vector>
#include <algorithm>
#include <map>
#include "mpi.h"
#include <time.h>


using namespace std;

// The rank of this process.
int Rank;

// The number of processes in the computation.
int Size;

// The starting index in the Item arrays that belong to process Rank.
int ItemBase;

// The ending index (MyItemCount - 1) of Items in the Item arrays that belong to process Rank.
int MyItemCount;

//Constructor
// argv: The command line arguments passed upon startup.
// argc: The number of elements in argv.
Solver :: Solver(int argc, char** argv)
{
    //Determine the rank of this process.
	MPI_Comm_rank(MPI_COMM_WORLD, &Rank);

	//Determine the number of processes in the computation.
	MPI_Comm_size(MPI_COMM_WORLD, &Size);

	SettingsContainer = new Settings();
	SettingsContainer -> GetSettings(argc, argv); //parse command line arguments
    //Only write the settings to the console if I am rank 0.
	if(Rank == 0)
	{
		SettingsContainer -> WriteSettings();
	}
    //Create a data structure representing the items, along with their value and costs,
    //and set the maximal cost.

	//Only create the data structure on the Rank 0 process.
	if(Rank == 0)
	{
		ReadData();
	}
}

//A function that returns a vector of items with weight that is less than or equal to (LEQ) i.
vector<Item*>* Solver::FindItemsLEQI(int i)
{
	//Create a new empty vector.	
	vector<Item*>* Candidates = new vector<Item*>();

	//Cycle through the items assigned to this process's rank.
	//fix: C4018
	for(unsigned j = 0; j < Items->size(); ++j)
	{
		Item* it = Items->at(j);
		//If the weight of item j is less than or equal to i...
		if(it->Cost() <= i)
		{
			//Create a new item and add it to the vector of items
			Candidates->push_back(it);
		}
	}

	//Return the newly created vector.
	return Candidates;
}

// MPI based method to solve the 0/1 Knapsack problem.
//
// The serial algorithm used here is described at http://en.wikipedia.org/wiki/Knapsack_problem. 
// It is in effect the following: A[i] = max(v_j + A[i-c_j] | c_j is less than or equal to i). 
// Note: It is assumed that for all items, the cost of the item is greater than zero.
int Solver :: Solve()
{
    //Broadcast the maximum cost constraint.
	MPI_Bcast(&MaximumCost, 1, MPI_INT, 0, MPI_COMM_WORLD);
	
    //Allocate the Answers array.
	Answers = new Solution*[MaximumCost + 1];

    //Create an answer for zero weight that has zero value.
	Solution *CurrentMax = new Solution(0, 0, NULL, NULL);

	vector<Item*>* CandidateItems = NULL;

    //The zero value solution is initially the best solution.
	Answers[0] = CurrentMax;

    //Broadcast the items read in from the input file.
	MPI_Bcast(&ItemCount, 1, MPI_INT, 0, MPI_COMM_WORLD);
	if(Rank != 0)
	{
		ItemWeight = new int[ItemCount];
		ItemValue = new int[ItemCount];
	}
	
	MPI_Bcast(ItemWeight, ItemCount, MPI_INT, 0, MPI_COMM_WORLD);
	MPI_Bcast(ItemValue, ItemCount, MPI_INT, 0, MPI_COMM_WORLD);

    //Limit the items used by this process to a subset.
	ItemBase = Rank * (ItemCount / Size);
	if(Rank != (Size - 1))
	{
		MyItemCount = ((ItemCount / Size) * (Rank + 1));
	}
	else 
	{
        //Be sure to include all of the items.
		MyItemCount = ItemCount;
	}

	Items = new vector<Item*>();
	for(int k = ItemBase; k < MyItemCount; ++k)
	{
		Items->push_back(new Item(ItemWeight[k], ItemValue[k], k));
	}

	//Allocate vectors for garbage collection.
	vector<Solution*>* SolutionGarbage = new vector<Solution*>();
	vector<vector<Item*>*>* VectorGarbage = new vector<vector<Item*>*>();
	vector<int*>* BufferGarbage = new vector<int*>();


	Solution *SubProblem = NULL;

	for(int i = 1; i <= MaximumCost; ++i)
	{
        //Get each item that can be considered at the current cost i.
		CandidateItems = FindItemsLEQI(i);

        //CurrentMax is always the best solution for the previous round when starting a new round.
		CurrentMax = Answers[i - 1]->Copy();

        //Determine the node-local maximum value solution.
        //For each item that can be considered
		for(unsigned j = 0; j < CandidateItems->size(); ++j)
		{
			Item* it = CandidateItems->at(j);

			//Get the optimal sub-problem for the remaining cost alottment
			SubProblem = Answers[i - it->Cost()];

			//If the cost of it and the sub-problem is less than i...
			if(SubProblem->Cost() + it->Cost() <= i)
			{
                //If the value of it and the sub-problem is greater than the current maximum...
				if(CurrentMax->Value() <= (it->Value() + SubProblem->Value()))
				{
		            //Make sure the sub-problem does not already contain it (this is the 0/1 constraint)
					if(!SubProblem->ContainsItem(it->Number()))
					{
						//Retain a reference to the solution for garbage colection.
						SolutionGarbage->push_back(CurrentMax);
                        //The best solution so far has been found for cost i
						CurrentMax = new Solution(SubProblem->Cost() + it->Cost(), SubProblem->Value() + it->Value(), it->Copy(), SubProblem->Copy());
					}
				}
			}
		}

		//Retain a reference to the CandidateItems vector for garbage collection.
		VectorGarbage->push_back(CandidateItems);


		//All reduce over our Solution objects.
		if(Rank == 0)
		{
			int* IncomingData = NULL;
			int IncomingDataLength = 0;
			MPI_Status Status;
			
			//Receive a solution from each of the participating processes.
			for(int u = 1; u < Size; ++u)
			{
				//Receive the number of integers being sent representing the solution object tree.
				MPI_Recv(&IncomingDataLength, 1, MPI_INT, u, 0, MPI_COMM_WORLD, &Status);

				//Allocate the recieve buffer.
				IncomingData = new int[IncomingDataLength];

				//Recieve the marshalled object tree.
				MPI_Recv(IncomingData, IncomingDataLength, MPI_INT, u, 0, MPI_COMM_WORLD, &Status);

				//Unmarshall the data into a Solution object tree.
				Solution* IncomingSolution = Solution::UnMarshall(IncomingData, IncomingDataLength/5);

				//Retain a handle to the buffer for garbage collection.
				BufferGarbage->push_back(IncomingData);

				//If the solution received is better than CurrentMax then replace CurrentMax.
				if(CurrentMax->Value() <= IncomingSolution->Value())
				{
					//Retain a handle to the old CurrentMax for garbage collection.
					SolutionGarbage->push_back(CurrentMax);

					CurrentMax = IncomingSolution;
				}
				else 
				{
					//Retain a handle to the new solution for garbage collection.
					SolutionGarbage->push_back(IncomingSolution);
				}
			}
		} 
		else 
		{
			int* OutgoingData;
			int OutgoingDataLen;

			//Marshall the Solution object tree into an array of integers.
			CurrentMax->Marshall(&OutgoingData, &OutgoingDataLen, 1);

			//Send the number of integers that are needed to represent the CurrentMax object tree.
			MPI_Send(&OutgoingDataLen, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);

			//Send the marshalled data in the OutgoingData buffer.
			MPI_Send(OutgoingData, OutgoingDataLen, MPI_INT, 0, 0, MPI_COMM_WORLD);

			//Retain a handle to the sent solution for garbage collection.
			SolutionGarbage->push_back(CurrentMax);

		}

		int* TheAnswer;
		int AnswerLen;
		//The rank zero process has the best overall solution for this round.
		//Time to send it out to all the processes.
		if(Rank == 0)
		{
			//Register the CurrentMax as the answer for round i.
			Answers[i] = CurrentMax->Copy();
			
			//Marshall the solution to send to all processes.
			CurrentMax->Marshall(&TheAnswer, &AnswerLen, 1);
			
			//Retain a handle to the solution for garbage collection.
			SolutionGarbage->push_back(CurrentMax);
			
			//Broadcast the number of int values needed to represent the solution.
			MPI_Bcast(&AnswerLen, 1, MPI_INT, 0, MPI_COMM_WORLD);

			//Broadcast the marshalled soultion.
			MPI_Bcast(TheAnswer, AnswerLen, MPI_INT, 0, MPI_COMM_WORLD);
		}
		else
		{
			//Receive the number of int values needed ot represent the solution.
			MPI_Bcast(&AnswerLen, 1, MPI_INT, 0, MPI_COMM_WORLD);
			
			//Allocate a buffer to receive the solution.
			TheAnswer = new int[AnswerLen];

			//Receive the solution.
			MPI_Bcast(TheAnswer, AnswerLen, MPI_INT, 0, MPI_COMM_WORLD);

			//Unmarshall and register the solution as the answer for round i.
			Answers[i] = Solution::UnMarshall(TheAnswer, AnswerLen/5);
	
			//Retain a handle to the buffer for later garbage collection.
			BufferGarbage->push_back(TheAnswer);

		}

		//do garbage collection
		for(unsigned a = 0; a < SolutionGarbage->size(); ++a)
		{
			delete SolutionGarbage->at(a);
		}
		SolutionGarbage->clear();
		for(unsigned a = 0; a < BufferGarbage->size(); ++a)
		{
			delete BufferGarbage->at(a);
		}
		BufferGarbage->clear();
		for(unsigned a = 0; a < VectorGarbage->size(); ++a)
		{
			delete VectorGarbage->at(a);
		}
		VectorGarbage->clear();
	}
	return 0;
}

//Input of results
void Solver::Finish(double time)
{
    if(Rank == 0)
    {

		printf("\r\n");
		printf("Clock time (sec): %.8f \r\n", time);  

        FILE* outputResult = 0;
        FILE* outputProfile = 0;

	   if( fopen_s(&outputProfile, SettingsContainer->profileFile , "wb")) 
		{
			printf("Can't create profile file!\r\n");            
			fclose(outputProfile);
			return;
		}

		if( fopen_s(&outputResult, SettingsContainer->resultsFile , "wb")) 
		{
			printf("Can't create result file!\r\n");   
			fclose(outputResult);
			return;
		}

		fprintf(outputProfile, "#Dwarfname:%s\r\n",SettingsContainer->dwarfName);

        char tmpbuf[1024];
        _tzset();
        
        _strdate_s( tmpbuf, 1024 );
        fprintf(outputProfile, "#Time: %s ",tmpbuf);

        _strtime_s( tmpbuf, 1024 );
        fprintf(outputProfile, "%s \r\n",tmpbuf);

        fprintf(outputProfile, "#Result time (sec): %.8f\r\n", time);  

        fprintf(outputResult, "The optimal solution for cost %d is:\r\n", MaximumCost);
        fprintf(outputResult, "Cost: %d, Value: %d\r\n", Answers[MaximumCost]->Cost(), Answers[MaximumCost]->Value());
        fprintf(outputResult, "With elements being:\r\n");
		fprintf(outputResult, Answers[MaximumCost]->ToString().c_str());

        fclose(outputProfile);
        fclose(outputResult);
    }
}

// Read the Item data, one Item value and associated cost per line, 
// into a list of Items.
//
//
// The first line of the file contains a single integer representing
// the maximum allowed cost C.
// The second line contains a single integer representing the number of elements in the input file.
// Each subsequent line contains two integer values for a given item: 
// 1) item cost, and
// 2) item value.
void Solver::ReadData()
{
	ifstream inf;

    //Open the file.
	inf.open(SettingsContainer -> inputFile, ios::in);

	//If there is an error then print a useful message and terminate.
	if(!inf)
	{
		cout  << "The file " << SettingsContainer -> inputFile << " could not be found." << endl;
		exit(1);
	}

    //Set the maximum cost for the solver.
	inf >> MaximumCost;

    //Set the number of items in the file.
	inf >> ItemCount;

	ItemWeight = new int[ItemCount];
	ItemValue = new int[ItemCount];

    //For each remaining line in the file:
	for(int i = 0; i < ItemCount; ++i)
	{
        //Create a new item with the associated cost and value of the given line
        //cost, value
		string comma;
		inf >> ItemWeight[i];
		inf >> comma;
		inf >> ItemValue[i];
	}

    //Close the file.
	inf.close();

}



Item::Item()
{
	myCost = 0;
	myValue = 0;
	myNumber = 0;
}
Item::Item(int cost, int value, int number)
{
	myCost = cost;
	myValue = value;
	myNumber = number;
}

// Format the Item's data in a string.
string Item::ToString()
{
	stringstream out;
	out << myNumber << ": " << myCost << ", " << myValue;
	return out.str();
}

// Copy the Item's data into a buffer.
void Item::Marshall(int* storage)
{
	storage[0] = myCost;
	storage[1] = myValue;
	storage[2] = myNumber;
}

// Create a copy of this item.
Item* Item::Copy()
{
	return new Item(myCost, myValue, myNumber);
}


Solution::Solution()
{
	myCost = 0;
	myValue = 0;
	myItem = 0;
	mySubSolution = 0;
}

Solution::Solution(int cost, int value, Item* item, Solution* subSolution)
{
	myCost = cost;
	myValue = value;
	myItem = item;
	mySubSolution = subSolution;
}

//A destructor that frees the entire object tree for Solution objects.
Solution::~Solution()
{
	if(myItem != NULL)
	{
		delete myItem;
	}
	if(mySubSolution != NULL)
	{
		delete mySubSolution;
	}
}

//Creates a copy of the Solution object tree.
Solution* Solution::Copy()
{
	return new Solution(myCost, myValue, (myItem == NULL)? NULL : myItem->Copy(), (mySubSolution == NULL)? NULL : mySubSolution->Copy());
}

// Format the data within this solution as a string.
string Solution::ToString()
{
	vector<Item> items;
	Solution *solution = this;
	while (solution != NULL) {
		if (solution->myItem != NULL)
			items.push_back(*(solution->myItem));
		solution = solution->mySubSolution;
	}
	sort(items.begin(), items.end());

	stringstream out;
	for (vector<Item>::iterator i = items.begin(); i != items.end(); i++) {
		out << i->ToString() << "\r\n";
	}
	return out.str();
}

// Tests whether this solution contains an item labeled with itemNumber.
// Returns true if an Item with the specified itemNumber is part of this solution.  False otherwise.
bool Solution::ContainsItem(int itemNumber)
{
	bool returnValue = false;

	//If I have an item...
	if(myItem != NULL)
	{
        //check to see whether itemNumber is my Item...
		if(myItem->Number() == itemNumber)
		{
            //if so -- return true
			returnValue = true;
		}
		else
		{
            //if not -- check mySubSolution to see if itemNumber is used there.
			if(mySubSolution != NULL)
			{
				returnValue = mySubSolution->ContainsItem(itemNumber);
			}
		}
	}
	return returnValue;
}

// Allocate an array of integers sufficiently large to store the entire solution object tree and
// copy the data of this object tree into the allocated array.
// This is a recursive function that increments count as more mySubSolution pointers are found to be valid.
// Arguments:
// data: A pointer to the newly allocated array that contains the data.
// len: A pointer to an integer representing the number of elements in data.
// count: An auxilary variable; the number of items in the solution.
void Solution::Marshall(int** data, int* len, int count)
{
	//If mySubSolution is null then we have reached the last solution in the tree are are ready to allocate memory for the array.
	if(mySubSolution == NULL)
	{
		//Count indicates how many Solution objects are in the tree.
		//Each solution takes five integer values to represent.
		*len = count * 5;

		//Allocate the array.
		*data = new int[*len];
	}
	else
	{
		//Recurse on the contained Solution.
		mySubSolution->Marshall(data, len, count+1);
	}
	int* storage = *data;
	
	//Solutions are stored _IN ORDER_ in the array -- the solution at the end of the object tree appears last in the array.
	int loc = (count-1) * 5;

	//Store the solution cost.
	storage[loc] = myCost;
	
	//Store the solution value.
	storage[loc + 1] = myValue;
	
	//If this solution contains a valid Item pointer...
	if(myItem != NULL)
	{
		//Store the item in the array.
		myItem->Marshall(&(storage[loc + 2]));
	}
	else
	{
		//Store -1 in the item location to indicate no item is present.
		storage[loc + 2] = -1;
		storage[loc + 3] = -1;
		storage[loc + 4] = -1;
	}
}

//Allocate and populate a Solution object tree from an array of integers.
//This is a recursive function that allocates more solutions depending on the NumberOfSolutions parameter passed.
//Arguments:
//Data: The int array that contains the solution data.
//NumberOfSolutions: The number of solutions contained in the Data array.
Solution* Solution::UnMarshall(int* data, int numberOfSolutions)
{
	return new Solution(data[0], 
						data[1], 
						(data[2] != -1)? new Item(data[2], data[3], data[4]): NULL, 
						(numberOfSolutions > 1)? UnMarshall(&data[5], numberOfSolutions - 1) : NULL);
}


